package com.cn.codebrush.字符串;

import java.util.ArrayList;
import java.util.List;

public class No17电话号码的字母组合 {
    public static void main(String[] args) {
        System.out.println(letterCombinations("2"));
    }

    /**
     * 回溯法
     * AC
     */
    static List<String> list = new ArrayList<>();
    public static List<String> letterCombinations(String digits) {
        if(digits.length() == 0){
            return list;
        }
        String[] strs = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
        letterCombinationsHelper(digits,strs,0);
        return list;
    }

    static StringBuilder builder = new StringBuilder();
    public static void letterCombinationsHelper(String digits,String[] strs,int num) {
        if(num == digits.length()){
            list.add(builder.toString());
            return;
        }

        String str = strs[digits.charAt(num)-'0'];
        for(int i=0;i<str.length();i++){
            builder.append(str.charAt(i));
            letterCombinationsHelper(digits,strs,num+1);
            builder.deleteCharAt(builder.length()-1);
        }

    }


}
